package com.zk.algorithm.math;

import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;

@LeetCodeExplore
@Medium
public class Sqrt {

    /**
     * 8 => 2
     * 9 => 3
     * 10 => 3
     * 11 => 3
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        int begin = 1;
        int end = x;
        int ans = begin;

        while (begin <= end) {
            int mid = begin + ((end - begin) >> 1);
            // =======================
            // BUG 1:
            //
            // int num = mid * mid;
            // 溢出问题
            //
            // BUG 2:
            // 除以 0 问题
            // =======================
            if (mid < x / mid) {
                begin = mid + 1;

                if (mid > ans) {
                    ans = mid;
                }
            } else if (mid > x / mid) {
                end = mid - 1;
            } else {
                return mid;
            }
        }

        return ans;
    }

}
